#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include "BinarySearchTree.h"
using namespace std;

template <typename Comparable>
void bstsort(vector<Comparable> &_arr, BinarySearchTree<Comparable> &bst)//此函数直接将输入的向量排序成为有序向量
{
  for(int i=0; i<_arr.size(); i++)
    bst.insert(_arr[i]);
  _arr.clear();
  bst.readTree(_arr);
}

template <typename Comparable>
void BSTSorting(vector<Comparable> &_arr, int _mode = 0)
{
  BinarySearchTree<Comparable> bst;
  if (_mode == 0)
    bstsort(_arr, bst);
  else
    {
      random_shuffle(_arr.begin(), _arr.end());
      bstsort(_arr, bst);
    }
}



int main()
{
  int n = 1000;
  double inf = 1;
  double sup = 10000;
  clock_t start,stop;
  vector<double> a(n);

  //生成n个大小位于区间inf~sup的随机数
  srand(time(0));
  for(int i=0; i<a.size(); i++)
  {
    a[i] = rand()/double(RAND_MAX)*(inf*(sup-inf-1)) + inf;
  }
  
  start = clock();
  BSTSorting(a, 0);
  stop = clock();
  cout << "_mode = 0" << endl;
  cout << "Use Time: " << double(stop-start) << "ms" << endl;
  cout << "---------------------------" << endl;

  
  start = clock();
  BSTSorting(a, 0);
  stop = clock();
  cout << "The worst case when _mode=0" << endl;
  cout << "Use Time: " << double(stop-start) << "ms" << endl;

  int lnum = 100;
  double aver = 0;
  for (int i=1; i<=lnum; i++)
    {
      start = clock();
      BSTSorting(a, 1);     
      stop = clock();
      aver = (aver*(i-1) + stop-start)/i;
    }
  cout << "The average case when _mode=1" << endl;
  cout << "Use Time: " << aver << "ms" << endl;
}
